package 树;

public class Demo01 {
    /*
    * 方法一: 递归回溯
    * 说实话,用递归回溯写这个题,差点被搞蒙了
    * 刚开始的时候tmp是全局的,到后面发现如果是全局的,那么tmp会跟着变化,起不到回溯的目的,将tmp改成局部变量
    * 直接过了
    * */
    static class Solution {
        int max = 0;
        int path = 0;
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            dfs(root);
            return max;
        }

        public void dfs(TreeNode root){
            path++;
            if(root.left == null && root.right == null){
                max = Math.max(path,max);
                return;
            }

            int tmp = path;
            if(root.left != null) dfs(root.left);
            path = tmp;
            if(root.right != null) dfs(root.right);
        }
    }

    /*
    * 深度优先搜索算法: 有时候换个思路也是一个可行的方法!
    * */
    static class Solution2 {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }

            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
